package com.njupt.DynamicProgramming;

import java.util.Scanner;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/14 13:38
 * @Description: 卡玛网57. 爬楼梯（第八期模拟笔试）
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 *
 * 每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？
 *
 * 注意：给定 n 是一个正整数。
 * @Version: 1.0
 */


public class KaMa_ClimbStairs_plus_57 {

    public int climbStairs(int n,int m){
        int[] dp = new int[n+1];
        dp[0] = 1;


        for (int i = 1; i <=n ; i++) { //遍历背包
            for (int j = 1; j <= m; j++) {  //遍历物品
                if(i>=j){
                    dp[i] += dp[i-j];
                }

            }
        }

        return dp[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        KaMa_ClimbStairs_plus_57 test = new KaMa_ClimbStairs_plus_57();
        int result = test.climbStairs(n,m);
        System.out.println(result);
    }
}
